package 题目集.线段树or树状数组.线段树;

import java.util.Arrays;

import org.junit.Test;

/**
 * https://leetcode.cn/problems/longest-increasing-subsequence/description/
 * 获取左侧比它小的长度最大值，单点修改和区间查询最大值（线段树）。
 */
public class demo01_最长上升子序列 {
	Node[] tree;
	int[] src;
	int n;

	public int lengthOfLIS(int[] nums) {
		n = nums.length;
		src=nums;
		agge(src);
		int tn = (int) Math.pow(2, 1 + Math.ceil(Math.log(n) / Math.log(2)));
		tree = new Node[tn];
		build(1, 1, n);
		int ans = 0;
		for (int i = 0; i < n; i++) {
			int cur=1;
			if(nums[i]>1) {
				cur=query(1, 1, nums[i] - 1) + 1;
			}
			ans = Math.max(ans, cur);
			update(1, nums[i], cur);
		}
		return ans;
	}

	private void build(int i, int l, int r) {
		tree[i] = new Node(l, r);
		if (l == r) {
			return;
		}
		int m = l + r >> 1;
		build(i << 1, l, m);
		build(i << 1 | 1, m + 1, r);
		pull(i);
	}

	public void pull(int i) {
		tree[i].max = Math.max(tree[i << 1].max, tree[i << 1 | 1].max);
	}

	public void update(int i, int index, int v) {
		if (tree[i].l == tree[i].r) {
			tree[i].max = v;
		} else {
			int m = tree[i].l + tree[i].r >> 1;
			if (index <= m)
				update(i << 1, index, v);
			else
				update(i << 1 | 1, index, v);
			pull(i);
		}
	}

	public int query(int i, int l, int r) {
		if (l <= tree[i].l && tree[i].r <= r) {
			return tree[i].max;
		} else {
			int m = tree[i].l + tree[i].r >> 1;
			int max = 0;
			if(l<=m) max=query(i<<1,l,r);
			if(m<r) max=Math.max(max, query(i<<1|1,l,r));
			return max;
		}
	}

	public void agge(int[] arr) {
		int[] sort = arr.clone();
		Arrays.sort(sort);
		for (int i = 0; i < arr.length; i++) {
			arr[i] = rank(sort, arr[i]);
		}
	}

	public int rank(int[] sort, int v) {
		int l = 0, r = sort.length - 1;
		while (l <= r) {
			int m = l + r >> 1;
			if (sort[m] < v) {
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		return l + 1;
	}
	static class Node {
		int l, r;
		int max;

		public Node(int l, int r) {
			super();
			this.l = l;
			this.r = r;
		}
	}
	
	@Test
	public void test() {
		int[] arr= {10,9,2,5,3,7,101,18};
		int len=lengthOfLIS(arr);
		System.out.println(len);
	}
}
